#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <queue>
#include <complex>
#include <cassert>
 
using namespace std;

const int inf = int(1e9);

class Graph {

public:
	vector <vector <pair <int, int> > > g;
	
	Graph() {}
	Graph(int n, vector <pair <int, pair <int, int> > > e) {
		g.resize(n);
		for (int i = 0; i < n; i++) {
			g[i].clear();
		}
		for (int i = 0; i < (int)e.size(); i++) {
			g[e[i].first].push_back(make_pair(e[i].second.first, e[i].second.second));
			g[e[i].second.first].push_back(make_pair(e[i].first, e[i].second.second));
		}
	}
	int get_vertices() {
		return (int)g.size();
	}
	pair <int, vector <pair <int, int> > :: iterator> get_iterator(int v) {
		return make_pair(v, g[v].begin());
	}
	bool valid(pair <int, vector <pair <int, int> > :: iterator> it){
		return it.second != g[it.first].end();
	}
	pair <int, vector <pair <int, int> > :: iterator> next(pair <int, vector <pair <int, int> > :: iterator> it){
		return make_pair(it.first, it.second + 1);
	}
	
};

int dijkstra(Graph g, int v, int u) {
	vector <bool> used;
	used.assign(g.get_vertices(), false);
	vector <int> d;
	d.assign(g.get_vertices(), inf);
	set <pair <int, int> > s;
	d[v] = 0;
	s.insert(make_pair(d[v], v));
	while (!s.empty()) {
		pair <int, int> cur = *(s.begin());
		s.erase(s.begin());
		if (cur.first == inf) {
			break;
		}
		used[cur.second] = true;
		pair <int, vector <pair <int, int> > :: iterator> e = g.get_iterator(cur.second);
		while (g.valid(e)) {
			if (d[(e.second)->first] > d[cur.second] + (e.second)->second) {
				if (!used[(e.second)->first]) {
					s.erase(make_pair(d[(e.second)->first], (e.second)->first));
				}
				d[(e.second)->first] = d[cur.second] + (e.second)->second;
				if (!used[(e.second)->first]) {
					s.insert(make_pair(d[(e.second)->first], (e.second)->first));
				}
			}
			e = g.next(e);
		}
	}
	return (d[u] == inf ? -1 : d[u]);
}

int main() {
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	int n, m;
	scanf("%d %d", &n, &m);
	vector <pair <int, pair <int, int> > > edges;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		a--;
		b--;
		edges.push_back(make_pair(a, make_pair(b, c)));
	}
	Graph g(n, edges);
	printf("%d\n", dijkstra(g, 0, n - 1));
	return 0;
}
